package sort;

import java.util.Arrays;
//冒泡排序时间复杂度为O(n^2)
//基本思想是:在每一次排序中,前后两个元素进行比较交换,每次排序后都把本次排序中的最大元素放到了最后面
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};

        int temp = 0;//用于交换的临时变量
        //外层循环为排序次数,循环次数为数组元素个数减1
        for (int i = 0; i < arr.length-1; i++) {
            //内层循环为每次排序中,元素间比较的次数,循环次数为数组元素个数减1再减去进行到第几次排序了,
            // 也就是外层循环变量i
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]) {//升序排序中前后两个元素进行比较,前一个元素比后一个元素大,就进行交换
                    temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));

        /*冒牌排序进行改进*/
        int[] arr1 = {3,9,-1,10,-2};

        int temp1 = 0;
        boolean flag = false;//辅助标记
        for (int i = 0; i < arr1.length-1; i++) {
            for (int j = 0; j < arr1.length-1-i; j++) {
                if(arr1[j]>arr1[j+1]) {
                    flag = true;//本次排序中,如果有元素进行交换,flag标记为true
                    temp1 = arr1[j];
                    arr1[j] = arr1[j+1];
                    arr1[j+1] = temp1;
                }
            }
            /*如果flag为false代表本次排序中,数组中的元素一次交换都没有进行,说明数组中的元素已经排序好了,
             就提前终止外层循环,后面的几次的排序就没有必要进行了,否则就把flag重新置为false,再看下次循环中,
             数组中的元素是否有交换
             */
            if(!flag) {
                break;
            }else {
                flag=false;
            }
        }
        System.out.println(Arrays.toString(arr1));
    }
}
